package com.Learning.sort;


import java.util.Arrays;

/**
 * 计数排序 CountingSort
 */
public class CountingSort {
    public int[] sortArray(int nums[]) {
        if (nums.length == 0) {
            return nums;
        }
        int bias, min = nums[0], max = nums[0];
        for(int i = 1; i < nums.length; ++i) {
            if (nums[i] > max) {
                max = nums[i];
            }
            if (nums[i] < min) {
                min = nums[i];
            }
        }
        bias = 0 - min;

        int[] countArray = new int[max - min + 1];
        Arrays.fill(countArray, 0);
        for(int i = 0; i < nums.length; ++i) {
            countArray[nums[i] + bias]++;
        }
        int index = 0;//原始数组下标
        int i = 0;// 计数数组下标
        while (index < nums.length) {
            // 只要计数数组中当前下标元素的值不为0 将计数数组中元素转换后
            // 重新写入原数组
            // 原理 计数数组的下标是原数组的值进行了偏移 只要将下标减去偏移量
            // 就能够得到原数组的值
            if (countArray[i] != 0) {
                nums[index] = i - bias;
                countArray[i]--;
                index++;
            } else {
                ++i;
            }
        }
        return nums;
    }
    // 寻找数组中的最大值 最小值
    // 用来获得 计数数组的容量

    // 遍历整个原始数组 将原始数组中每个元素值转化为数组下标
    // 并将数组下标对应的元素值大小进行累加


}
/*
计数排序 是一个排序时不比较元素大小的排序算法
对一定范围内 的整数排序时候 素的非常快
一般快于其他排序算法 但计数排序局限性比较大
只限于对整数进行排序 而且排序元素值分布教连续 跨度小的情况
 */
